/*
binary search
*/

#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstdlib>

const int NUM = 100;
int array[NUM];

void prepareData(int* array, int n)
{
	int i;
	for (i = 0; i < n; i ++)
		array[i] = i;
}

/*
find x in array
return -1 or the index of x
*/
int binarySearch(int* array, int n, int x)
{
	int l, r, mid;
	l = 0;
	r = n - 1;

	while ( l <= r )
	{
		mid = l + ((r-l)>>1);		
		if ( array[mid] == x )
			return mid;
		else if ( array[mid] < x )
			l = mid + 1;
		else
			r = mid - 1;
	}
	return -1;
}

int main ()
{
	int i, j, tmp;
	prepareData(array, NUM);
	srand(time(NULL));
	for (i = 1; i <= 10; i ++)
	{
		for (j = 0; j < 100; j ++)
		{
			tmp = rand() % 200;
			printf("find %d in %d array: %d\n", tmp, i, binarySearch(array, i, tmp));
		}
	}
	return 0;
}